package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/house-robber-ii/
 *
 * @Author: haogege
 * @Date: 2021/9/11
 */
public class _213_打家劫舍II {

    public static void main(String[] args) {

        _213_打家劫舍II ii = new _213_打家劫舍II();

        int[] ints = {1, 7, 9, 2};
        System.out.println(ii.rob(ints));

    }

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        return Math.max(robMain(nums, 0, nums.length - 1), robMain(nums, 1, nums.length));
    }

    public int robMain(int[] nums, int begin, int end) {
        int len = end - begin;
        if (len == 1) return nums[begin];
        int[] dp = new int[len];
        // 初始化dp数组
        dp[0] = nums[begin];
        dp[1] = Math.max(nums[begin], nums[begin + 1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < len; i++) {
            int mapToDpIndex = i + begin;
            dp[i] = Math.max(dp[i - 2] + nums[mapToDpIndex], dp[i - 1]);
        }
        return dp[len - 1];
    }

    public int rob2(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robTest(nums, 0, nums.length - 1), robTest(nums, 1, nums.length));
    }

    // 滚动数组优化
    public int robTest(int[] nums, int begin, int end) {
        int len = end - begin;
        if (len == 1) return nums[begin];
        int[] dp = new int[2];
        // 初始化dp数组
        dp[0] = nums[begin];
        dp[1] = Math.max(nums[begin], nums[begin + 1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < len; i++) {
            int mapToDpIndex = i + begin;
            dp[i & 1] = Math.max(dp[i - 2 & 1] + nums[mapToDpIndex], dp[i - 1 & 1]);
        }
        return dp[len - 1 & 1];
    }

    public int robTest2(int[] nums, int begin, int end) {
        int len = end - begin;
        if (len == 1) return nums[begin];
        int[] dp = new int[len];
        // 初始化dp数组
        dp[0] = nums[begin];
        dp[1] = Math.max(nums[begin], nums[begin + 1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < len; i++) {
            int mapToDpIndex = i + begin;
            dp[i] = Math.max(dp[i - 2] + nums[mapToDpIndex], dp[i - 1]);
        }
        return dp[len - 1];
    }

    // 1 2 3 1
    public int robTest1(int[] nums, int begin, int end) {
        int len = end - begin;
        if (len == 1) return nums[begin];
        int[] dp = new int[len];
        // 初始化dp数组
        dp[0] = nums[begin];
        dp[1] = Math.max(nums[begin], nums[begin + 1]);
        // 存在的情况，也就是偷与不偷的情况
        int beginIndex = begin + 2;
        for (int i = beginIndex; i < end; i++) {
            int mapToDpIndex = i - begin;
            dp[mapToDpIndex] = Math.max(dp[mapToDpIndex - 2] + nums[i], dp[mapToDpIndex - 1]);
        }
        return dp[len - 1];
    }

}
